package com.lagou;

public class Test02 {
    public static int maxValue(int[] values, int[] weights, int max) {
        if (values == null || values.length == 0) return 0;
        if (weights == null || weights.length == 0) return 0;
        if (values.length != weights.length || max <= 0) return 0;
        //dp数组
        int[][] dp = new int[values.length + 1][max + 1];
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= max; j++) {
                //选择的物品超过最大承重
                if (j < weights[i - 1]) {
                    //最大价值=上一轮的最大价值（不选择该物品）
                    dp[i][j] = dp[i - 1][j];
                }
                //可选择该物品
                else {
                    //上一轮的最大价值（不选择该物品） ，选择该物品 两者的最大值
                    dp[i][j] = Math.max((dp[i - 1][j]), values[i - 1] + dp[i - 1][j - weights[i - 1]]);
                }
            }
        }
        return dp[values.length][max];
    }

    public static void main(String[] args) {
        int[] gold = {600, 300, 500, 400, 600};
        int[] man = {2, 2, 5, 5, 4};
        int max = 10;
        System.out.println(maxValue(gold, man, max));
    }
}
